﻿namespace LeetCodeProject._0001_1000._001_100._51_60._052;

public class Solution
{
    public int TotalNQueens(int n)
    {
        HashSet<int> columns = new HashSet<int>();
        HashSet<int> diagonals1 = new HashSet<int>();
        HashSet<int> diagonals2 = new HashSet<int>();
        return Backtrack(n, 0, columns, diagonals1, diagonals2);
    }

    private int Backtrack(int n, int row, HashSet<int> columns, HashSet<int> diagonals1, HashSet<int> diagonals2)
    {
        if (row == n)
        {
            return 1;
        }
        else
        {
            int count = 0;
            for (int i = 0; i < n; i++)
            {
                if (columns.Contains(i))
                {
                    continue;
                }

                int diagonal1 = row - i;
                if (diagonals1.Contains(diagonal1))
                {
                    continue;
                }

                int diagonal2 = row + i;
                if (diagonals2.Contains(diagonal2))
                {
                    continue;
                }

                columns.Add(i);
                diagonals1.Add(diagonal1);
                diagonals2.Add(diagonal2);
                count += Backtrack(n, row + 1, columns, diagonals1, diagonals2);
                columns.Remove(i);
                diagonals1.Remove(diagonal1);
                diagonals2.Remove(diagonal2);
            }

            return count;
        }
    }
}